import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=56 lang=java
 *
 * [56] 合并区间
 *
 * https://leetcode-cn.com/problems/merge-intervals/description/
 *
 * algorithms
 * Medium (34.26%)
 * Total Accepted:    8.9K
 * Total Submissions: 26.1K
 * Testcase Example:  '[[1,3],[2,6],[8,10],[15,18]]'
 *
 * 给出一个区间的集合，请合并所有重叠的区间。
 * 
 * 示例 1:
 * 
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 
 * 
 * 示例 2:
 * 
 * 输入: [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * 
 */
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() < 2) {
            return intervals;
        }
        intervals.sort((a, b) -> {
            if (a.start < b.start) {
                return -1;
            } else if (a.start > b.start) {
                return 1;
            } else if (a.end < b.end) {
                return -1;
            } else if (a.end > b.end) {
                return 1;
            } else {
                return 0;
            }
        });
        List<Interval> ret = new LinkedList<>();
        Interval first = intervals.get(0);
        int l = first.start, r = first.end;
        for (int i=1; i<intervals.size(); ++i) {
            Interval next = intervals.get(i);
            if (next.start <= r) {
                r = r > next.end ? r : next.end;
            } else {
                ret.add(new Interval(l, r));
                l = next.start;
                r = next.end;
            }
        }
        ret.add(new Interval(l, r));
        return ret;
    }
}
